package com.learn.algorithm.graph;

import java.util.ArrayDeque;
import java.util.Deque;

public class LeetCode1368 {
    public static int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] distance = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        Deque<int[]> queue = new ArrayDeque<>();

        int[][] move = {{}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        distance[0][0] = 0;
        queue.add(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] record = queue.pollFirst();
            int x = record[0];
            int y = record[1];
            if (x == m - 1 && y == n - 1) {
                return distance[x][y];
            }
            for (int i = 1; i < 5; i++) {
                int nx = x + move[i][0];
                int ny = y + move[i][1];
                int weight = grid[x][y] == i ? 0 : 1;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && distance[x][y] + weight < distance[nx][ny]) {
                    distance[nx][ny] = weight + distance[x][y];
                    if (weight == 0) {
                        queue.addFirst(new int[]{nx, ny});
                    } else {
                        queue.addLast(new int[]{nx, ny});
                    }
                }
            }
        }
        return -1;
    }
}
